package dfs;

/**
 * leet-code(200) 岛屿数量
 *
 * @author Ringo
 * @date 2021/9/1 13:15
 */
public class NumIslands {

    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        System.out.println(numIslands(grid));
    }

    public static int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        boolean[][] visited = new boolean[m][n];
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    ++count;
                    dfs(grid, i, j, visited, directions);
                }
            }
        }
        return count;
    }

    /**
     * 递归
     *
     * @param grid       数组
     * @param m          当前横坐标
     * @param n          当前纵坐标
     * @param visited    访问数组
     * @param directions 方向
     */
    public static void dfs(char[][] grid, int m, int n, boolean[][] visited, int[][] directions) {
        if (grid[m][n] != '1') return;

        visited[m][n] = true;

        for (int[] direct : directions) {
            int a = m + direct[0], b = n + direct[1];
            if (a < 0 || b < 0 || a >= grid.length || b >= grid[0].length) continue;
            if (visited[a][b]) continue;
            dfs(grid, a, b, visited, directions);
        }
    }

}
